// Package _2___III__从上到下打印二叉树_III main
// @Title _2___III__从上到下打印二叉树_III
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-10 11:23
// @Create  2022-02-10 11:23
package main

import "fmt"

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var ans [][]int
	tag := 0
	myQueue := []*TreeNode{root}
	for len(myQueue) > 0 {
		size := len(myQueue)
		tempArr := []int{}
		for i := 0; i < size; i++ {
			//
			t := myQueue[0]
			myQueue = myQueue[1:]
			tempArr = append(tempArr, t.Val)
			if t.Left != nil {
				myQueue = append(myQueue, t.Left)
			}
			if t.Right != nil {
				myQueue = append(myQueue, t.Right)
			}
		}
		if tag%2 != 0 {
			for i := 0; i < len(tempArr)/2; i++ {
				tempArr[i], tempArr[len(tempArr)-1-i] = tempArr[len(tempArr)-1-i], tempArr[i]
			}
		}
		ans = append(ans, tempArr)
		tag++
	}
	return ans
}

func main() {
	root := TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val:   9,
			Left:  nil,
			Right: nil,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val:   15,
				Left:  nil,
				Right: nil,
			},
			Right: &TreeNode{
				Val:   7,
				Left:  nil,
				Right: nil,
			},
		},
	}
	fmt.Println(levelOrder(&root))
}
